package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1156 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maxRepOpt1(String text) {
            Map<Integer, Integer> prev = new HashMap<>();// 此处记录当前窗口数字出现的最早位置
            Map<Integer, Integer> after = new HashMap<>();// 此处记录当前窗口数字出现的最晚位置
            int n = text.length();

            for (int i = 0; i < n; i++) {
                int num = text.charAt(i) - 'a';
                if (!prev.containsKey(num)) prev.put(num, i);
            }

            for (int i = n - 1; i >= 0; i--) {
                int num = text.charAt(i) - 'a';
                if (!after.containsKey(num)) after.put(num, i);
            }

            int ans = 0, left = 0, right = 0, curWindowNum = text.charAt(0) - 'a', curWindowUnMatchCnt = 0,
                    curWindowUnMatchPos = 0, curWindowSwapPos = -1, curWindowCanSwapUseOutOf = 0;
            while (right < n) {
                int num = text.charAt(right) - 'a';
                if (num != curWindowNum) {
                    curWindowUnMatchCnt++;
                    if (curWindowUnMatchCnt > 1) {
                        // 需要重置窗口，定位到第一次失配的位置
                        left = curWindowUnMatchPos;
                        right = curWindowUnMatchPos;
                        curWindowNum = text.charAt(curWindowUnMatchPos) - 'a';
                        curWindowUnMatchCnt = 0;
                        curWindowCanSwapUseOutOf = 0;
                        curWindowSwapPos = -1;
                    } else {
                        curWindowUnMatchPos = right;// 记录第一次失配位置
                        // 当前还可以用窗口外的数字填补
                        if (prev.get(curWindowNum) < left || after.get(curWindowNum) > right) {
                            curWindowCanSwapUseOutOf = 1;
                            curWindowSwapPos = prev.get(curWindowNum) < left ? prev.get(curWindowNum) : (after.get(curWindowNum) > right ? after.get(curWindowNum) : -1);
                            ans = Math.max(ans, right - left + 1);
                        }
                    }
                } else {
                    int unMatchHappenInsideWindow = (curWindowSwapPos > -1 && curWindowSwapPos >= left && curWindowSwapPos <= right) ? 1 : 0;
                    ans = Math.max(ans, right - left + 1 - curWindowUnMatchCnt + curWindowCanSwapUseOutOf - unMatchHappenInsideWindow);
                }

                right++;
            }

            curWindowCanSwapUseOutOf = (prev.get(curWindowNum) < left || after.get(curWindowNum) > right) ? 1 : 0;
            return Math.max(ans, right - left - curWindowUnMatchCnt + curWindowCanSwapUseOutOf);
        }
    }


    public void run() {
        System.out.println(new Solution().maxRepOpt1("ababa"));
        System.out.println(new Solution().maxRepOpt1("aaabaaa"));
        System.out.println(new Solution().maxRepOpt1("aaabbaaa"));
        System.out.println(new Solution().maxRepOpt1("aaaaa"));
        System.out.println(new Solution().maxRepOpt1("abcdef"));
        System.out.println(new Solution().maxRepOpt1("bbababaaaa"));
        System.out.println(new Solution().maxRepOpt1("babbaaabbbbbaa"));
    }

    public static void main(String[] args) throws Exception {
        LC1156 an = new LC1156();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
